#include "grid.h"

CostType Grid::initialCost() {
	// Factors: 
	// 1. Number of vertical cell rows passed through, including passover cell of terminals
	// 2. Horizontal distance
	// BOZO: each two terminal net distance calculated (Semiperimeter needed?)
	cerr << "Initializing Cost..." << endl;
	for(CellType i = 0; i < n; i++) {	//calculate for each cell
		// add cost to grid
		CostType cell = cellCost(i, false);
		cells[i].cost = cell;
		costs[i] = cell;
		totalCost += cell;
		cell = 0;
	}
	return totalCost;
}

void Grid::vertHeightCalc(CellType index, CellType j, CellType k, PositionType &start, PositionType &end, bool &dir, CellType &startCell) {
	// changes start and end to the ends of the vertical height
	// start < end always, if feedthrough cell required, that row is included
	// direction indicates horizontal diretion from start to end, false=left, true=right/line
	CostType verticalCost = cells[cells[index].terminal[j][k].cellNum].position[1]-cells[index].position[1]; // |y1-y0|
	PositionType x0, x1;

	// start and end rows for the net, will need feedthrough if this is greater than 1
	if (verticalCost < 0) {
		// y1 above y0; (less)
		// start is y1
		start = cells[cells[index].terminal[j][k].cellNum].position[1];
		end = cells[index].position[1];
		x0 = cells[cells[index].terminal[j][k].cellNum].position[0];
		x1 = cells[index].position[0];
		startCell = x1;
		if(!cells[index].isBottom(j, false)) {
			// if terminal not on bottom, no feedthrough needed
			end--;
		}
		if(cells[cells[index].terminal[j][k].cellNum].isBottom(cells[index].terminal[j][k].termNum, false)) {
			start++;
		}
		if((x0-x1) <= 0) {
			dir = false;
		}
		else {
			dir = true;
		}
	}
	else if (verticalCost > 0){
		start = cells[index].position[1];
		end = cells[cells[index].terminal[j][k].cellNum].position[1];
		x0 = cells[index].position[0];
		x1 = cells[cells[index].terminal[j][k].cellNum].position[0];
		startCell = x0;
		if(cells[index].isBottom(j, false)) {
			start++;
		}
		if(!cells[cells[index].terminal[j][k].cellNum].isBottom(cells[index].terminal[j][k].termNum, false)) {
			end--;
		}
		if((x0-x1) <= 0) {
			dir = true;
		}
		else {
			dir = false;
		}
	}
	else {
		// they are in the same row
		start = cells[cells[index].terminal[j][k].cellNum].position[1];
		end = cells[index].position[1];
		x0 = cells[cells[index].terminal[j][k].cellNum].position[0];
		x1 = cells[index].position[0];
		startCell = x1;
		if(!((cells[index].isBottom(j, false) && !cells[cells[index].terminal[j][k].cellNum].isBottom(cells[index].terminal[j][k].termNum, false))||(!cells[index].isBottom(j, false) && cells[cells[index].terminal[j][k].cellNum].isBottom(cells[index].terminal[j][k].termNum, false)))) {
			end--;
		}
		if((x0-x1) <= 0) {
			dir = false;
		}
		else {
			dir = true;
		}
	}

}

void Grid::feedthroughCalc() {
	// calculates feedthrough cells needed for each row
	totalFeedthrough = 0;
	for(CellType i = 0; i < n; i++) {	//calculate for each cell
		CellType index = i;
		for(CellType j = 0; j < 4; j++) {									//each terminal
			for(unsigned int k = 0; k < cells[index].terminal[j].size(); k++) {	//each net
				PositionType start, end;
				bool temp_0;
				CellType temp_1;
				vertHeightCalc(index, j, k, start, end, temp_0, temp_1);
				// increment each row the net will pass through
				for(PositionType l = start; l <= end; l++) {
					// increment all rows
					if(l == start) {
						// if this loop is reached, the net requires a feedthrough
//						cerr << cells[index].terminal[j][k].cellNum << ", " << cells[index].terminal[j][k].termNum << endl;
						feedthroughList.insert(pair<CellType,TerminalNode>(cells[index].terminal[j][k].netNum, cells[index].terminal[j][k]));
					}
					feedthrough[l]++;
				}
			}
		}
	}
	// adjust all feedthroughs because each net counted twice
	maxFeedthrough = 0;
	for(unsigned short int l = 0; l < feedthrough.size(); l++) {
		feedthrough[l] /= 2;
		totalFeedthrough += feedthrough[l];
		if (feedthrough[l] > maxFeedthrough) {
			maxFeedthrough = feedthrough[l];
		}
	}	
}
	
CostType Grid::cellCost(CellType index, bool swapTest, PositionType x, PositionType y, bool flip) {
	CostType cellCost = 0;
	CostType verticalCost = 0;
	PositionType x0, y0;
	if (index >= 0) {
		if(swapTest) {
			// this is a cost of possible switch, use new position values
			x0 = x;
			y0 = y;
		}
		else {
			// this is a calculation based on real location
			x0 = cells[index].position[0];
			y0 = cells[index].position[1];
		}
		for(CellType j = 0; j < 4; j++) {									//each terminal
			for(unsigned int k = 0; k < cells[index].terminal[j].size(); k++) {	//each net
				CostType tempCost = abs(cells[cells[index].terminal[j][k].cellNum].position[0]-x0); // |x1-x0|
				verticalCost = cells[cells[index].terminal[j][k].cellNum].position[1]-y0; // |y1-y0|
				// if verticalCost is positive, y1 below y0
				if(verticalCost < 0 ) {
					// y1 above y0
					verticalCost = -verticalCost;
					if(cells[index].isBottom(j, flip))
						verticalCost++;
					if(!cells[cells[index].terminal[j][k].cellNum].isBottom(cells[index].terminal[j][k].termNum, flip))
						verticalCost++;
				}
				else if(verticalCost > 0) {
					// y1 below y0
					if(!cells[index].isBottom(j, flip))
						verticalCost++;
					if(cells[cells[index].terminal[j][k].cellNum].isBottom(cells[index].terminal[j][k].termNum, flip))
						verticalCost++;
				}
				else {
					// y1 == y0
					if((cells[index].isBottom(j, flip) && !cells[cells[index].terminal[j][k].cellNum].isBottom(cells[index].terminal[j][k].termNum, flip))||(!cells[index].isBottom(j, flip) && cells[cells[index].terminal[j][k].cellNum].isBottom(cells[index].terminal[j][k].termNum, flip)))
						verticalCost++;
				}
				tempCost = (tempCost)+(25*verticalCost);
				cellCost += tempCost;
			}
		}
		return cellCost;
	}
	else {
		// location was empty, so no cost
		return 0;
	}
}

void Grid::swap(PositionType x0, PositionType y0, PositionType x1, PositionType y1, bool flip0, bool flip1) {
	// swap the nodes and update with the new costs
	// swap nodes
	if(cellGrid[y0][x0] >= 0) {
		if(flip0) {
			cells[cellGrid[y0][x0]].toggleFlip();
		}
		cells[cellGrid[y0][x0]].setPosition(x1, y1);
	}
	if(cellGrid[y1][x1] >= 0) {
		if(flip1) {
			cells[cellGrid[y1][x1]].toggleFlip();
		}
		cells[cellGrid[y1][x1]].setPosition(x0, y0);
	}
	CellType tempNode = cellGrid[y0][x0];
	cellGrid[y0][x0] = cellGrid[y1][x1];
	cellGrid[y1][x1] = tempNode;
	// update the costs of cells and total cost
	updateCost(cellGrid[y0][x0]);
	updateCost(cellGrid[y1][x1]);
}

void Grid::updateCost(CellType index) {
	if (index >= 0) {
		cells[index].cost = cellCost(index, false);
		totalCost -= (costs[index] - cells[index].cost); // subtract improvement from totalCost
		costs[index] = cells[index].cost; //update costs vector
		for(int i = 0; i < 4; i++) { // for each terminal
			for(unsigned int j = 0; j < cells[index].terminal[i].size(); j++) { // for each cell in list
				CellType tempIndex = cells[index].terminal[i][j].cellNum;
				cells[tempIndex].cost = cellCost(tempIndex, false);
				totalCost -= (costs[tempIndex] - cells[tempIndex].cost); // subtract improvement from totalCost, add unimprovement back to cost
				costs[tempIndex] = cells[tempIndex].cost; //update costs vector
			}
		}
	}
	else {
	}
}

CostType Grid::swapCostImprove(PositionType x0, PositionType y0, PositionType x1, PositionType y1, bool &flip0, bool &flip1) {
	// calculate new total cost if cell swap were made
	// a swap of the two will result in same wires between the two
	// BOZO: one does not know about the mirroring of the other
	CostType improvement = 0, improvement_noFlip = 0, improvement_Flip = 0;
	if(cellGrid[y0][x0] >= 0) {
		improvement_noFlip = (costs[cellGrid[y0][x0]] - cellCost(cellGrid[y0][x0], true, x1, y1, false));
		improvement_Flip = (costs[cellGrid[y0][x0]] - cellCost(cellGrid[y0][x0], true, x1, y1, true));
		if(improvement_noFlip < improvement_Flip) {
			improvement += improvement_Flip;
			flip0 = true;
		}
		else {
			improvement += improvement_noFlip;
			flip0 = false;
		}
	}
	if(cellGrid[y1][x1] >= 0) {
		improvement_noFlip = (costs[cellGrid[y1][x1]] - cellCost(cellGrid[y1][x1], true, x0, y0, false));
		improvement_Flip = (costs[cellGrid[y1][x1]] - cellCost(cellGrid[y1][x1], true, x0, y0, true));
		if(improvement_noFlip < improvement_Flip) {
			improvement += improvement_Flip;
			flip1 = true;
		}
		else {
			improvement += improvement_noFlip;
			flip1 = false;
		}
	}
	return improvement;
}

void Grid::optimizePlace() {
	// SA to optimize
	// pick cells at random, possible switch with empty
	double T = 1000000;
	double M = 100; // repetitions of metropolis function
	double alpha = .8;
	double beta=1.05;
	unsigned int count=0;
	double R;
	unsigned int COUNTA = 20, COUNTB = 100;

	PositionType x0, y0, x1, y1;
	bool flip0, flip1;

	cerr << "Annealing";
	while (T > .1) { // outer loop criteria
		int i = 0;
		if(count == COUNTA) {
			alpha = .95;
		}
		else if (count == COUNTB) {
			alpha = .8;
		}
		while(i < M) { // inner loop criteria
			// assign values for test switch
			x0 = rand() % squareSide;
			y0 = rand() % squareSide;
			x1 = rand() % squareSide;
			y1 = rand() % squareSide;
			CostType improvement = swapCostImprove(x0, y0, x1, y1, flip0, flip1);
			R = rand()/32767.0;
			if( improvement > 0 || R < exp(improvement/T)) {
				// do the swap
				swap(x0, y0, x1, y1, flip0, flip1);
			}
			i++;
		}
		T *= alpha;
		M *= beta;
		count++;
		cerr << ".";
	}
	cerr << endl;

}
	
void Grid::initialPlace() {
	// randomly place the cells in the grid
	int randRow, randCol;
	int possible = squareSide*squareSide;
	for(CellType i = 0; i < n;) {
		randRow = rand() % possible;
		randCol = randRow % squareSide;
		randRow = randRow / squareSide;
		// make sure this grid location is empty
		if(cellGrid[randRow][randCol] == -1) {
			cellGrid[randRow][randCol] = i;
			cells[i].setPosition(randCol,randRow);
			i++;
		}
	}
}	

void Grid::place() {
	cerr << "Initializing Place..." << endl;
	initialPlace();
	initialCost();
	optimizePlace();
	feedthroughCalc();
}